【题解】 [SCOI2010]股票交易 单调队列优化DP luoguP2569 | Qiuly's blog!

【题解】 [SCOI2010]股票交易 单调队列优化DP luoguP2569

Posted on | Edited on | In | Comments:

我们一起来推一推。

设 $f[i][j]$ 表示：现在是第 $i$ 天，手上拥有的股票数为 $j$ 时赚到的最多的钱

我们考虑转移几个方向：空手买，不买不卖，之前买过了现在继续买，买过后需要卖

空手买

空手买就是第一次买，显然不要考虑 “间隔 $w$ 天” 的限制，直接买就好。

那么很容易得到转移式：

因为是买入，所以是负数。

不买不卖

很显然可以直接从 $f[i-1][j]$ 转移过来。

转移式：

之前买过了现在继续买

很显然这次我们需要考虑 $w$ 的限制了，不过我们可以直接从 $i-w-1$ 天转移。

假设我们是从 $f[i-w-1][k]$ 转移过来的，那么这次转移我们多买了 $j-k$ 张股票，容易得到转移式：

当然因为规定了一天最多买入 $AS_i$ 股，上面的式子必须满足 $j-AS_i\leq k \leq j$

买过之后需要卖

同样的有 $w$ 的限制，但是跟上面的第三种情况没什么两样，转移式：

因为 $BS_i$ 的限制条件，上面的式子必须满足 $j\leq k \leq j+BS_i$

时间复杂度？

枚举 $i,j$ 状态就需要 $n^2$ 的复杂度，在这个基础上转移的复杂度为：

  • 空手买 ： $O(1)$
  • 不买不卖 ： $O(1)$
  • 之前买过了现在继续买 ：$O(n)$
  • 买过之后需要卖 ：$O(n)$

会发现如果加上枚举状态的复杂度，后面两个转移的总复杂度为 $O(n^3)$ ！

于是考虑优化。

我们观察第三个转移式：

对于当前的 $i,j$ ，假设有 $a,b$ 作为 $k$ 的两个选项对 $f[i][j]$ 进行转移，我们算一算 $a$ 比 $b$ 优的条件是什么：

这里我们会发现 $j\times AP_i$ 跟里面的式子没有任何关系，提出来不会产生仍和影响

于是我们发现我们只需要得到最大的 $f[i-w-1][k]+k\times AP_i$ 就好了，这里我们可以用到单调队列优化DP 。

具体代码实现如下：

1
2
3
4
5
6
7
l=1,r=0;
for(int j=0;j<=MaxP;++j) {/*枚举所有的合法的j*/
    while(l<=r&&q[l]<j-AS) ++l;/*淘汰掉过期的队头*/
    while(l<=r&&f[i-W-1][q[r]]+q[r]*AP<=f[i-W-1][j]+j*AP) --r;/*淘汰掉不如当前决策优的队尾*/
    q[++r]=j;/*当前决策进队*/
    if(l<=r) f[i][j]=max(f[i][j],f[i-W-1][q[l]]+q[l]*AP-j*AP);/*转移*/
}

因为每一个状态都只进队/出队了一次，所以可以证明时间复杂度现在变为 $O(n^2)$ 了。

第四个操作一样可以这样优化，可以尝试一下，不贴解释了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=2e3+2;
const int inf=1e9+9;

int T,MaxP,W,AP,BP,AS,BS,l,r;
int q[N],f[N][N];
int main() {
    memset(f,128,sizeof(f));/*赋极小值*/
    scanf("%d%d%d",&T,&MaxP,&W);
    for(int i=1;i<=T;++i) {
        scanf("%d%d%d%d",&AP,&BP,&AS,&BS);
        for(int j=0;j<=AS;++j) f[i][j]=-AP*j;
        for(int j=0;j<=MaxP;++j) f[i][j]=max(f[i][j],f[i-1][j]);
        if(i<=W)continue;
        l=1,r=0;
        for(int j=0;j<=MaxP;++j) {
            while(l<=r&&q[l]<j-AS) ++l;
            while(l<=r&&f[i-W-1][q[r]]+q[r]*AP<=f[i-W-1][j]+j*AP) --r;
            q[++r]=j;
            if(l<=r) f[i][j]=max(f[i][j],f[i-W-1][q[l]]+q[l]*AP-j*AP);
        }
        l=1,r=0;
        for(int j=MaxP;j>=0;--j) {
            while(l<=r&&q[l]>j+BS) ++l;
            while(l<=r&&f[i-W-1][q[r]]+q[r]*BP<=f[i-W-1][j]+j*BP) --r;
            q[++r]=j;
            if(l<=r) f[i][j]=max(f[i][j],f[i-W-1][q[l]]+q[l]*BP-j*BP);
        }
    }
    int ans=0;
    for(int i=0;i<=MaxP;++i)ans=max(ans,f[T][i]);
    printf("%d\n",ans);
    return 0;
}